<!DOCTYPE html>

<html>
<head>
    <meta charset="utf-8" />
    <title>TopCoder SRM 647 - 500: CtuRobots</title>
    
    <link type="image/x-icon" rel="shortcut icon" href="http://www.topcoder.com/i/favicon.ico"/>
    

    
    <style type="text/css">
        /* font */
body {
    font-family: Helvetica, Arial, Verdana, sans-serif;
    font-size: 16px;
    line-height: 1.2em;
}
ul.constraints > li:before, ul.notes > li:before {
    font-family: monospace;
    font-weight: normal;
}
.heading {
    font-weight: bold;
    font-size: 175%;
    line-height: 1.2em;
}
.section .section-title {
    font-weight: bold;
    font-size: 125%;
}
ol.testcases > li:before {
    font-family: monospace;
}
type {
    font-weight: bold;
    font-family: monospace;
}
li.testcase .data {
    font-family: monospace;
    line-height: 1.5em;
}

/* layout */
.heading {
    margin-top: 0.1em;
    margin-bottom:0.1em;
    text-align: center;
}
.section .section-title {
    margin-top : 1em;
    margin-bottom: 1em;
}
.problem-intro, note, user-constraint {
    padding-left: 1.25em;
}

/* Lists */
ul.constraints, ul.notes, ul.variables, ul.problem-definition-lines {
    list-style-type: none;
    padding: 0px;
}
ul.constraints > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}
ul.notes > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}

/* Testcases */
li.testcase {
    line-height: 1.1em;
    padding-top: 0.625em;
    padding-bottom: 0.625em;
    overflow: auto;
}
li.testcase > .testcase-content > div { padding-bottom: 0.5em; padding-left: 1em; }

li.testcase .testcase-comment {
    margin: 0;
    padding-left: 1em;
}
.testcase-comment p:first-child { margin-top: 0; }
.testcase-comment p:last-child { margin-bottom: 0; }

li.testcase .testcase-content {
    margin: 0.31em;
}

/* Data and variables */
.testcase-output {
    padding: 0.2em 1em 0.2em 0em;
}
.variables, .testcase-output {
    margin-left: 0.5em;
    display: table;
    margin-bottom: 0px;
    margin-top: 0px;
}
.variable {
    display: table-row;
}
.variable .name {
    padding: 0.2em 0em 0.2em 1em;
    font-weight: bold;
    display: table-cell;
    text-align: right;
}
.testcase-output .prefix {
    padding: 0.2em 0em 0.2em 1em;
    display: table-cell;
}
.testcase-output .prefix:after {
    content : ":";
    padding-right: 0.5em;
}
.variable .name:after {
    font-weight: bold;
    content : ":";
    padding-right: 0.5em;
}
.variable .value, .testcase-output .value {
    padding: 0.2em 1em 0.2em 0em;
    display: table-cell;
}
ol.testcases {
    padding: 0px;
    counter-reset: test_number -1;
}
ol.testcases > li {
    list-style:none;
}
ol.testcases > li:before {
    counter-increment:test_number;
    display: block;
    clear: both;
    content:counter(test_number) ")";
    color: inherit;
    background: inherit;
}

/* Problem Definition */
.problem-definition, .problem-limits {
    padding-left: 1.25em;
}
.problem-definition-lines, .limit-lines {
    display: table;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-left: 0px;
}
.definition-line, .limit-line {
    display: table-row;
    height: 1.5em;
    overflow: auto;
}
.limit-name:after {
    content: ":";
    margin-right: 1em;
}
.definition-name, .definition-value, .limit-name, .limit-value {
    display: table-cell;
}
.definition-value {
    padding-left: 0.5em;
}
.definition-name:after {
    content: ":";
}
#contest-division:before {
    content: "Div ";
}
#problem-score:before {
    content: "- Problem ";
}
#problem-name {
    display: block;
}

/* Tags, hidden default */
.tag {
    visibility: hidden;
    position: absolute;
}

        body {
    /* font color */
    color: #333333;
    /* background color */
    background-color: white;
}
.section .section-title {
    /* title color */
    color: black;
}
li.testcase .data {
    /* highlight color */
    background: #eee;
}

    </style>
    
    
    

</head>

<body>
    <h1 class="heading">
        <span id='contest-name'>SRM 647</span>
        <span id='contest-division'>1</span>
        <span id='problem-score'>500</span>
        <span id='problem-name'>CtuRobots</span>
    </h1>

    <hr />

    <!-- Problem Statement -->
    <div class="section">
        <h2 class="section-title">Problem Statement</h2>
        <div class="problem-intro">
            <intro escaped="1">Cat Ctu is going to buy some robots.
His budget is <b>B</b> dollars.
You are given <type>int[]</type>s <b>cost</b> and <b>cap</b> that describe a store.
For each valid i, the store sells one robot that costs <b>cost</b>[i] dollars and has a fuel tank that can hold at most <b>cap</b>[i] units of fuel.
Initially, all robots have a full fuel tank.
Ctu can purchase any subset of these robots, as long as he does not exceed his budget.
<br />
<br />
Once Ctu purchases some robots, he will number them sequentially, starting from 1.
Note that he may number them in any order - he is not required to preserve the order in which the robots' parameters are given in <b>cost</b> and <b>cap</b>.
<br />
<br />
The robots are going to travel along a straight line.
They will all start at the position 0 on the line.
Ctu wants to send a robot as far as possible in the positive direction.
Precise rules of robot movement are given below.
<br />
<ul>
<li>The robots' movement is continuous. They are able to travel arbitrary positive real distances.</li>
<li>Moving 1 unit of distance consumes 1 unit of fuel.</li>
<li>The robots will initially all travel together in the positive direction. One by one, in the order given by their numbers, the robots will then turn back. Multiple robots with consecutive numbers may turn back at the same position.</li>
<li>Each robot must return back to position 0.</li>
<li>As a robot turns back, it can donate any amount of fuel to the next robot. (I.e., for each valid k, robot k may donate some of its fuel to robot k+1. Note that after the donation robot k must still have enough fuel to get back to position 0.)</li>
<li>The amount of fuel a robot carries can never exceed the initial capacity of its fuel tank.</li>
</ul>
<br />
Given that Ctu buys the optimal subset of robots he can afford, and given that he then numbers and programs them optimally, compute and return the largest position that can be reached by one of Ctu's robots.</intro>
        </div>
    </div>
    
    <!-- Problem definition -->
    
    <div class="section" id="definition">
        <h2 class="section-title">Definition</h2>
        <div class="problem-definition">
            <ul class="problem-definition-lines">
                <li class="definition-line" id='class-line'>
                    <span class='definition-name'>Class</span>
                    <span class='definition-value'>CtuRobots</span>
                </li>
                <li class="definition-line" id='method-line'>
                    <span class='definition-name'>Method</span>
                    <span class='definition-value'>maxDist</span>
                </li>
                <li class="definition-line" id='parameters-line'>
                    <span class='definition-name'>Parameters</span>
                    <span class='definition-value'>
                    
                        integer
                    , 
                        tuple(integer)
                    , 
                        tuple(integer)
                    
                    </span>
                </li>
                <li class="definition-line" id='returns-line'>
                    <span class='definition-name'>Returns</span>
                    <span class='definition-value'>
                        float
                    </span>
                </li>
                <li class="definition-line" id='signature-line'>
                    <span class='definition-name'>Method signature</span>
                    <span class='definition-value'>
                        def maxDist(self, B, cost, cap)
                    </span>
                </li>
            </ul>
            <div class="problem-definition-public-tip">(be sure your method is public)</div>
        </div>        
    </div>
    

    <!-- Limits -->
    <div class="section">
        <h2 class="section-title">Limits</h2>
        <div class='problem-limits'>
            <ul class="limit-lines">
                <li class='limit-line'>
                    <span class='limit-name'>Time limit (s)</span>
                    <span class='limit-value'>2.000</span>
                </li>
                <li class='limit-line'>
                    <span class='limit-name'>Memory limit (MB)</span>
                    <span class='limit-value'>256</span>
                </li>
            </ul>
        </div>
    </div>

    
    <!-- Notes -->
    <div class="section">
        <h2 class="section-title">Notes</h2>
        <ul class="notes">
        
            <li><note escaped="1">Your return value must have an absolute or relative error smaller than or equal to 1e-6</note></li>
        
        </ul>
    </div>
    
    
    <!-- Constraints -->
    <div class="section">
        <h2 class="section-title">Constraints</h2>
        <ul class="constraints">
        
            <li><user-constraint escaped="1"><b>B</b> will be between 1 and 10,000, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1"><b>cost</b> will have between 1 and 500 elements, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1"><b>cap</b> will have exactly the same number of elements as <b>cost</b>.</user-constraint></li>
        
            <li><user-constraint escaped="1">Each element of <b>cost</b> will be between 0 and <b>B</b>, inclusive.</user-constraint></li>
        
            <li><user-constraint escaped="1">Each element of <b>cap</b> will be between 0 and 1,000,000,000, inclusive. </user-constraint></li>
        
        </ul>
    </div>

    <!-- Test cases -->
    <div class="section">
        <h2 class="section-title">Test cases</h2>
        <ol class="testcases" start='0'>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">B</span>
                                <span class="value data">
                                
                                    100
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cost</span>
                                <span class="value data">
                                
                                    { 50, 25 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cap</span>
                                <span class="value data">
                                
                                    { 1, 1 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            0.6666666666666666
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment">In this case, Ctu has a budget of 100 dollars.
He can buy both robots for 50+25 = 75 dollars.
One of the robots will get the number 1 and the other will get the number 2.
If they cooperate, one of these robots can reach the position 2/3 = 0.666666667.
Here's how an optimal program looks like:
Both robots travel together to the position 1/3.
At this moment, each of them has 2/3 of a unit of fuel in its fuel tank.
Robot 1 donates 1/3 of a unit of fuel to robot 2 and turns back.
Robot 2 now has a full fuel tank again.
It continues to the position 2/3.
There it turns back and returns to position 0.</div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">B</span>
                                <span class="value data">
                                
                                    25
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cost</span>
                                <span class="value data">
                                
                                    { 23, 5, 8, 20, 15 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cap</span>
                                <span class="value data">
                                
                                    { 108, 30, 42, 100, 94 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            55.0
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">B</span>
                                <span class="value data">
                                
                                    1382
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cost</span>
                                <span class="value data">
                                
                                    { 0, 0, 0, 1000, 1000, 0, 1000, 0 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cap</span>
                                <span class="value data">
                                
                                    { 2039, 4819, 5923, 1577, 8749, 9182, 3652, 4918 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            6503.238683127572
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">B</span>
                                <span class="value data">
                                
                                    209
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cost</span>
                                <span class="value data">
                                
                                    { 185, 130, 109, 1, 45, 117, 127, 13, 2, 37, 6, 1, 2 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cap</span>
                                <span class="value data">
                                
                                    { 93, 5, 278, 4, 20, 54, 93, 213, 103, 5, 225, 32, 5 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            190.48376771833563
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">B</span>
                                <span class="value data">
                                
                                    9956
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cost</span>
                                <span class="value data">
                                
                                    { 3229, 736, 1325, 2680, 410, 1227, 1378, 499, 1525, 1722, 1262, 2080, 2581, 1505, 1019, 480, 3155, 836, 2697, 616, 136, 2032, 2345, 3154, 1953, 1654, 344, 3079, 1426, 199, 2857, 1714, 2952, 996, 1567, 2674, 2054, 2110, 949, 2412, 2148, 1016, 234, 1932, 1554, 1943, 1625, 1266, 258, 2924, 49, 1693, 3140, 309, 557, 12, 2760, 227, 2497, 330, 646, 1935, 3032, 2671, 2433, 164, 1472, 3080, 717, 221, 2483, 1309, 1174, 12, 917, 2335, 3086, 148, 64, 189, 2628, 1660, 2983, 109, 1920, 2470 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cap</span>
                                <span class="value data">
                                
                                    { 934850, 214, 15807606, 2426, 176520, 1900009, 1184867, 40550, 1774843, 2953, 77834310, 7276, 3139890, 695, 213862217, 13, 193864, 189, 557664, 1206555, 85133, 381662, 4887, 115027, 2186890, 218075, 1, 2024, 9, 95244962, 7, 906, 3485642, 52962078, 58645759, 785706, 303, 18, 189, 819600, 17528041, 11616471, 92719012, 82351, 12752, 634, 26122233, 215485, 58, 5506810, 101874, 130429471, 2, 1, 68966, 76303, 321766922, 463, 26, 225, 207, 52, 1739, 246841, 496, 228, 4749453, 191, 79, 10560, 1414194, 7529, 13, 521935, 1, 2, 11590618, 4020, 105, 3, 28, 3, 2855, 189909573, 1, 295052 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            2.1034261053998655E8
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">B</span>
                                <span class="value data">
                                
                                    8852
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cost</span>
                                <span class="value data">
                                
                                    { 2547, 912, 2592, 1085, 296, 523, 2257, 2347, 1822, 261, 334, 2159, 528, 2739, 201, 964, 427, 2038, 26, 2361, 234, 2063, 2885, 2178, 2708, 730, 2902, 326, 306, 2794, 1725, 13, 137, 2169, 388, 1124, 1464, 2120, 2357, 1544, 2794, 2260, 185, 650, 2852, 124, 1767, 453, 1331, 1397, 1991, 1166, 413, 1428, 2862, 1194, 1139, 571, 1299, 1232, 267, 2027, 746, 1971, 2695, 2586, 185, 1319, 1088, 2818, 2604, 1798, 475, 1252, 1767, 2277, 545, 601, 2160, 325, 2749, 1161, 1172, 1075, 1925, 2468, 1596, 1116, 1558, 2226, 1302, 796, 775, 1105, 418, 334, 2872, 1921, 2830, 2448, 2914, 2634, 1386, 2516, 492, 1029, 1134, 2934, 2017, 1741, 1675, 2593, 2233, 2401, 68, 683, 2053, 155, 183, 923, 2276, 1823, 65, 2290, 2448, 92, 2468, 819, 837, 303, 1440, 705, 291, 2348, 2562, 765, 1926, 14, 2514, 2403, 2671, 1143, 1358, 121, 376, 2874, 2447, 1769, 1686, 967, 967, 2492, 2472, 2014, 1686, 2291, 1093, 1801, 818 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">cap</span>
                                <span class="value data">
                                
                                    { 263268, 256181, 476791, 365614, 265352, 19307, 243180, 84909, 98175, 367524, 241474, 479623, 277638, 111229, 155356, 415525, 234382, 97870, 451466, 58375, 268277, 404582, 484789, 458230, 529286, 449840, 103208, 199505, 319373, 294746, 78005, 326456, 14418, 257144, 135669, 238651, 411723, 99122, 20421, 298154, 278407, 153564, 24778, 73065, 110408, 392693, 510192, 362399, 333830, 125893, 130946, 345134, 261418, 230632, 306751, 451242, 175675, 459988, 150787, 349338, 134594, 255227, 263645, 180770, 436965, 502871, 242085, 318340, 220576, 189202, 395789, 390659, 101649, 337117, 440471, 466547, 513054, 316694, 30382, 38826, 472506, 67698, 223953, 397305, 325564, 57949, 194651, 443500, 443188, 431386, 220061, 400640, 286085, 189461, 324214, 171813, 420711, 260549, 426526, 208052, 83343, 429483, 366076, 52443, 224742, 333286, 544259, 335276, 93282, 326772, 82841, 225256, 270357, 547610, 397526, 193336, 182374, 439866, 255860, 111363, 509167, 228847, 218257, 39438, 212242, 378338, 88972, 127544, 59230, 428847, 155553, 116333, 255176, 396356, 223463, 226360, 38283, 6238, 173455, 447707, 332111, 60485, 398523, 462205, 55397, 148417, 529738, 460063, 177715, 404809, 336155, 50750, 24165, 530386, 394811, 512481, 230296, 45797, 370008 }
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            408339.73124862404
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
        </ol>
    </div>
    <hr />

    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
</body>
</html>
